1. Field of the Invention
The present invention relates to signal processing, and, more specifically but not exclusively, to preamble detection for wide-band code-division multiple access (WCDMA) and other wireless standards.
2. Description of the Related Art
In WCDMA and other wireless standards, user equipment, such as cell phones, transmit preambles to inform base transceiver stations (BTSs) that the user equipment (UE) is available to establish a connection with the network. In systems that adhere to the 3GPP standards, the preamble, which is transmitted on the physical random access channel (PRACH), is a 4,096-chip sequence comprising 256 repetitions of a 16-bit signature code. The 3GPP standard allows for up to 16 different signature codes, commonly referred to as the 16 Hadamard codes, and often, only a subset of the 16 possible signature codes is employed in a given system. Before transmitting, the signature code is scrambled using a long scrambling code. The scrambling code is constructed from scrambling sequences, and there are 8,192 PRACH preamble scrambling codes in total.
When transmitting a preamble, the user equipment randomly chooses one of the available signature codes, scrambles the signature with a preamble scrambling code, and transmits the resulting preamble at the beginning of a WCDMA Acquisition Indicator Channel (AICH) access slot. There are 15 access slots per two frames, and the slots are spaced 5,120 chips apart. The BTS typically does not know a priori which of the randomly chosen signature codes was used in constructing the preamble. Further, the BTS typically does not know the length of the propagation delay of the preamble (i.e., the delay between the time the preamble was transmitted and the time that the preamble is received) because the location of the user equipment within the cell in which the BTS resides is typically unknown to the BTS at the time a connection is requested.
Since the preamble is the first indication of the user equipment to the BTS, the BTS detects the user equipment by correlating received data at the beginning of each AICH access slot. PRACH preamble detection is typically performed by means of implementing a matched filter for each possible signature code in the subset of signature codes. In particular, the received data is correlated with all possible preambles for each signature code in the subset of signature codes and for each possible propagation delay for the cell. Although the particular preamble that was transmitted is not known a priori to the BTS, the BTS typically knows a priori all of the possible preambles that could have been transmitted. The result of these correlations is a correlation profile for each possible signature code, where each correlation profile has a number of values (herein referred to as “correlation profile values” or simply “profile values”) that is equal to the number of possible delays. In other words, the total number of correlation profiles is equal to the number of possible signature codes, and the total number of correlation profile values is equal to the number of possible signature codes times the number of possible delays. The correlation profile value for signature s and delay lag may be represented as shown in Equation (1):
                              profile          ⁡                      (                          s              ,              lag                        )                          =                                                      ∑                              i                =                0                                            L                -                1                                      ⁢                                          sm                i                            ⁢                              c                                  s                  ,                  i                                            ⁢                              x                                  i                  +                  lag                                                                                                  (        1        )            where smi is the ith chip of the scrambling code multiplied by
      ⅇ          j      ⁡              (                              π            4                    +                                    π              2                        ⁢            ⅈ                          )              ,cs,i is the ith chip of the signature code s, and xi+lag is the (i+lag)th chip of received data corresponding to possible delay lag. Note that here i is the chip index, j is the square root of negative one, and L is the preamble length in chips (e.g., 4,096 chips). Further, as used herein, the term “scrambling code” refers to a scrambling code that is modified by multiplying each chip of the scrambling code by
      ⅇ          j      ⁡              (                              π            4                    +                                    π              2                        ⁢            ⅈ                          )              .
After all correlation profiles are generated, each correlation profile value is compared to a preamble-detection threshold to detect the signature code that was transmitted and one or more possible propagation delays between the user equipment and the BTS. Each of the one or more possible propagation delays corresponds to a different propagation path of the transmitted preamble. The one or more possible propagation delays may then be provided to a path searcher component to detect the propagation delay of the propagation path that is received first in time. Discussions of preambles and preamble detection may be found in Third Generation Partnership Project (3GPP) Technical Specification (TS) 25.211 V9.1.0 (2009-12) “Physical Channels and Mapping of Transport Channels onto Physical Channels (FDD),” 3GPP TS 25.213 V9.1.0 (2009-12) “Spreading and Modulation (FDD),” and 3GPP TS 25.214 V9.2.0 (2010-03) “Physical Layer Procedures (FDD),” the teachings of all of which are incorporated herein by reference in their entirety.
When a relatively large number of signature codes are employed (e.g., all 16 Hadamard codes), separately performing the above-mentioned matched filter approach for each signature code becomes relatively computationally expensive. In this case, a more-efficient approach to detecting preambles may be employed that is based on the Fast Hadamard Transform by rewriting Equation (1) as shown in Equation (2):
                              profile          ⁡                      (                          s              ,              lag                        )                          =                                                      ∑                              k                =                0                            15                        ⁢                          [                                                c                                      s                    ,                    k                                                  ⁢                                                      ∑                                          l                      =                      0                                                                                      L                        /                        16                                            -                      1                                                        ⁢                                                            sm                                                                        16                          ⁢                          l                                                +                        k                                                              ⁢                                          x                                                                        16                          ⁢                          l                                                +                        k                        +                        lag                                                                                                        ]                                                                    (        2        )            where i=16l+k and k corresponds to one of the 16 bits in a signature sequence where k=0, . . . , 15. Equation (2) is derived from the fact that every signature s comprises 256 repetitions of a 16-bit sequence. As shown in Equation (2), the signature code cs,k is broken out into an outer-most summation. The inner-most summation is performed 16 times, once for each bit k of a 16-bit signature code sequence, to generate 16 partial correlation values pc(k, lag) for the signature s, where
      pc    ⁡          (              k        ,        lag            )        =            ∑              l        =        0                              L          /          16                -        1              ⁢                  sm                              16            ⁢            l                    +          k                    ⁢                        x                                    16              ⁢              l                        +            k            +            lag                          .            
Essentially, Equation (2) divides the chips of received data x, and the corresponding chips of the scrambling code sm, into 16 streams, each stream corresponding to a different bit k of a 16-bit signature code sequence. The chips of received data x are split up and assigned to 16 streams such that received data chips x0, x1, . . . , x15 are distributed to streams 0, 1, . . . , 15, respectively, received data chips x16, x17, . . . , x31 are distributed to streams 0, 1, . . . , 15, respectively, and so forth. Note that each partial correlation value pc(k, lag) may be generated by coherently accumulating all L/16 chips. Alternatively, the L/16 chips can divided into smaller groups, where the chips in each group are coherently accumulated, and then the magnitudes or squares of resulting coherent accumulations are non-coherently accumulated to generate the partial correlation value pc(k, lag).
As a result of the signature code cs,k being broken out into an outer-most summation, the inner-most summation is independent of the signature codes, and therefore, the 16 partial correlations that result from the inner-most summation may be reused for all 16 signature codes. The correlation profiles for all 16 signatures are derived by multiplying the 16×16 Hadamard Matrix with the 16 partial correlations from the inner summation as shown in Equation (2). Such calculation may be accelerated by using the Fast Hadamard Transformation.
Even though the Fast Hadamard Transform approach is more efficient than the matched filter approach, the Fast Hadamard Transform approach still has a computational expense that is relatively high. This is due to the relatively large number of correlations that are performed across the numerous signature codes and delays. Therefore, there is a need for even more-efficient methods of preamble detection that reduce the total number of correlations that are needed to detect preambles without negatively impacting detection accuracy.